#include "all.h"
#include "Imm.h"
#include "Optimizer.h"


ImmCodes* CodeOptimizer::optimize(ImmCodes* in) {

	#ifndef TEST_FINAL
	in->print(cout);
	#endif 

	ImmCodes* out;

	BasicBlockManager::getManager()->resetAllCode(in);


	bool updated;
	updated = true;

	//Remove dummy blocks
	updated = true;
	BasicBlockManager::getManager()->resetAllCode();

	bool updated1, updated2, updated3, updated4, updated5;

	//for (int i=0; i<10; i++){
	while (updated){
		updated1 = false;
		BasicBlockManager::getManager()->iterativeOptimizeBasicBlocks(&updated1);

		updated2 = true;
		while (updated2)
			BasicBlockManager::getManager()->optimizeJumpThread(&updated2);

		BasicBlockManager::getManager()->resetAllCode();

		updated3 = false;
		BasicBlockManager::getManager()->iterativeDataFlowAnalysis(&updated3);

		updated4 = true;
		while (updated4)
			BasicBlockManager::getManager()->removeEmptyBlocks(&updated4);

		BasicBlockManager::getManager()->resetAllCode();

		updated5 = false;
		BasicBlockManager::getManager()->resetAllCode(peephole_main(BasicBlockManager::getManager()->getCode(), &updated5));
		updated = updated1 || updated2 || updated4 || updated3 || updated5;
	}

	return BasicBlockManager::getManager()->getCode();
}



ImmCodes*
CodeOptimizer::peephole_main(ImmCodes* in, bool* updatedIn) {
	ImmCodes* out = new ImmCodes();
	vector<ImmCode*>* window;
	*updatedIn = false;
	bool updated;

	window = new vector<ImmCode*> ();

	/* reorderJump
	 * ********************************
	 */
	window->push_back(in->get_code()->at(0));
	window->push_back(in->get_code()->at(1));

	for (int i = 2; i < in->get_code()->size(); i++) {
		window->push_back(in->get_code()->at(i));
		peephole_reorderJump(window);
		if (window->size() == 3) {
			out->add(window->at(0));
			window->erase(window->begin());
		}
		else
			*updatedIn = true;
	}
	for (int i = 0; i < window->size(); i++)
		out->add(window->at(i));

	ImmCodes* out2 = new ImmCodes();

	/* removeJumpToNextAddr
	 * ********************************
	 */
	window = new vector<ImmCode*> ();
	window->push_back(out->get_code()->at(0));

	for (int i = 1; i < out->get_code()->size(); i++) {
		window->push_back(out->get_code()->at(i));
		peephole_removeJumpToNextAddr(window);
		if (window->size() == 2) {
			out2->add(window->at(0));
			window->erase(window->begin());
		}
		else
			*updatedIn = true;
	}
	for (int i = 0; i < window->size(); i++)
		out2->add(window->at(i));

	ImmCodes* out3 = new ImmCodes();

	/* removeConsecutiveGOTO
	 * ********************************
	 */
	window->clear();
	window->push_back(out2->get_code()->at(0));

	for (int i = 1; i < out2->get_code()->size(); i++) {
		window->push_back(out2->get_code()->at(i));
		peephole_removeConsecutiveGOTO(window);
		if (window->size() == 2) {
			out3->add(window->at(0));
			window->erase(window->begin());
		}
		else
			*updatedIn = true;
	}
	for (int i = 0; i < window->size(); i++)
		out3->add(window->at(i));

	ImmCodes* out4 = new ImmCodes();

	/* remove useless label
	 * ********************************
	 */
	window->clear();
	window->push_back(out3->get_code()->at(0));

	for (int i = 1; i < out3->get_code()->size(); i++) {
		window->push_back(out3->get_code()->at(i));
		peephole_removeUselessLabel(window);
		if (window->size() == 2) {
			out4->add(window->at(0));
			window->erase(window->begin());
		}
		else
			*updatedIn = true;
	}
	for (int i = 0; i < window->size(); i++)
		out4->add(window->at(i));
	


	ImmCodes* out5 = new ImmCodes();

	/* remove redundant arithmetic operation
	 * ********************************
	 */
	window->clear();
	bool updated5 = false;

	for (int i = 0; i < out4->get_code()->size(); i++) {
		window->push_back(out4->get_code()->at(i));
		peephole_removeRedundantArithmetic(window, &updated5);
		if (window->size() == 1) {
			out5->add(window->at(0));
			window->erase(window->begin());
			*updatedIn = *updatedIn || updated5;
		}
		else
			*updatedIn = true;
	}
	for (int i = 0; i < window->size(); i++)
		out5->add(window->at(i));


	return out5;

}

void CodeOptimizer::peephole_removeJumpToNextAddr(vector<ImmCode*>* window,
		bool* updated) {
	/*Optimize for
	 *
	 * Modify:
	 * 		goto L7
	 * L7:
	 *
	 * To:
	 * L7:
	 */

	ImmCode *goto_node, *label_node;

	if (window->size() != 2)
		return;

	if ((window->at(0)->getType() == ImmCode::GOTO) && window->at(1)->getType()
			== ImmCode::LABEL) {
		goto_node = window->at(0);
		label_node = window->at(1);

		void** opnd = goto_node->get_opnd();
		string goto_label = ((ImmCode*) (opnd[0]))->labelName();

		unsigned int id = (long) (label_node->get_opnd()[0]);
		string *name = (string*) (label_node->get_opnd()[1]);
		ostringstream os;
		if (name && name->length())
			os << *name;
		else
			os << "L" << id;

		if ((goto_label != os.str())) {
			return;
		}

		window->clear();
		window->push_back(label_node);

	}
	return;

}

void CodeOptimizer::peephole_reorderJump(vector<ImmCode*>* window,
		bool* updated) {
	/*Optimize for
	 *
	 Modify:
	 if a2 goto L6
	 goto L5
	 L6:

	 To:
	 if a2 == 0 goto L5
	 L6:

	 */

	ImmCode *if_node, *middle_node, *label_node, *if_node_new;

	if (window->size() != 3)
		return;

	if ((window->at(0)->getType() == ImmCode::IF || window->at(0)->getType()
			== ImmCode::IF_REL) && window->at(2)->getType() == ImmCode::LABEL) {
		if_node = window->at(0);
		middle_node = window->at(1);
		label_node = window->at(2);

		void** opnd = if_node->get_opnd();
		string if_label = ((ImmCode*) (opnd[0]))->labelName();
		ImmCode* new_label;

		unsigned int id = (long) (label_node->get_opnd()[0]);
		string *name = (string*) (label_node->get_opnd()[1]);
		ostringstream os;
		if (name && name->length())
			os << *name;
		else
			os << "L" << id;

		if ((middle_node->getType() != ImmCode::GOTO) || (if_label != os.str())) {
			return;
		}

		void** opnd1 = middle_node->get_opnd();
		new_label = ((ImmCode*) (opnd1[0]));

		window->clear();

		if (if_node->getType() == ImmCode::IF)
			if_node_new = new ImmCode(ImmCode::IF_REL, OpNode::EQ, new_label,
					opnd[1], (void*) new ValueNode(new Value(0, Type::INT)));
		else {
			if_node_new = if_node;
			opnd[0] = new_label;
			if_node_new->reverse_subcode();
		}

		window->push_back(if_node_new);
		window->push_back(label_node);

	}

	return;

}

void CodeOptimizer::peephole_removeConsecutiveGOTO(vector<ImmCode*>* window,
		bool* updated) {
	/*Optimize for
	 *
	 * Modify:
	 * 		goto L7
	 * 		goto L8
	 *
	 * To:
	 * 		goto L7
	 */

	ImmCode *goto_node;

	if (window->size() != 2)
		return;

	goto_node = window->at(0);

	if ((window->at(0)->getType() == ImmCode::GOTO) && window->at(1)->getType()
			== ImmCode::GOTO) {
		window->clear();
		window->push_back(goto_node);
	}
	return;

}


void CodeOptimizer::peephole_removeUselessLabel(vector<ImmCode*>* window, bool* updated){

	/*Optimize for
	 *
	 * Modify:
	 * 		inst xxx
	 *   Ly:
	 *      ...
	 *      
	 *      if Ly is not used in anywhere
	 * To:
	 * 		inst xxx
	 *      ... 
	 */
	
	ImmCode *inst_node, *label_node;

	if (window->size() != 2)
		return;
	
	if (window->at(0)->getType() == ImmCode::GOTO || window->at(0)->getType()
			== ImmCode::IF || window->at(0)->getType() == ImmCode::IF_REL)
		return;

	if (window->at(1)->getType() != ImmCode::LABEL)
		return;

	inst_node = window->at(0);
	label_node = window->at(1);



	void** opnd = label_node->get_opnd();

	unsigned int id = (long) (label_node->get_opnd()[0]);
	string *name = (string*) (label_node->get_opnd()[1]);
	ostringstream os;
	if (name && name->length())
		os << *name;
	else
		os << "L" << id;


	if (os.str().substr(0, 8) == "_action_" || os.str().substr(0, 1) != "L")
		return;

	vector<BasicBlock*>* allBlocks = BasicBlockManager::getManager()->getAllBlocks();

//	cout << "mmmmmmmm\n\n\nPossible: "<< os.str() << "nmmmmmmmmmm\n\n\n";


	//Search for the number of times a block is used
	int* blockRefCounter = (int*) malloc(sizeof(int) * allBlocks->size());
	memset(blockRefCounter, 0, sizeof(int) * allBlocks->size());
	for (int i = 0; i < allBlocks->size(); i++) {
		for (int j = 0; j < allBlocks->at(i)->getNextBlocks()->size(); j++) {
			for (int k = 0; k < allBlocks->size(); k++)
				if (allBlocks->at(i)->getNextBlocks()->at(j)
						== allBlocks->at(k)->getLabel())
					blockRefCounter[k]++;
		}
	}

	for (int i = 0; i < allBlocks->size(); i++)
		if (allBlocks->at(i)->getLabel() == os.str()) {
			if (blockRefCounter[i] == 0) { // || (blockRefCounter[i] == 1 && )
				window->clear();
				window->push_back(inst_node);
			}
			break;
		}

	free(blockRefCounter);

	return;
}


void
CodeOptimizer::peephole_removeRedundantArithmetic(
		vector<ImmCode*>* window, bool* updated) {
	*updated = false;
	/*Optimize for
	 *
	 * Modify:
	 * 		a1 = a1 + 0
	 *
	 * To:
	 * 		//Removed
	 */

	ImmCode *input_node;

	if (window->size() != 1)
		return;

	if (window->at(0)->getType() == ImmCode::EXPR) {
		input_node = window->at(0);
		ExprNode** opd = (ExprNode**) (input_node->get_opnd());
		ExprNode* node0 = opd[0];
		ExprNode* node1 = opd[1];
		ExprNode* node2 = opd[2];

		if (node2 == NULL){
			if (node1 == node0)
				goto remove_instruction;
			return;
		}

		//exactly only one of the node is value node
		if ( node2->exprNodeType() != ExprNode::VALUE_NODE &&  node1->exprNodeType() != ExprNode::VALUE_NODE)
			return;

		if ( node2->exprNodeType() == ExprNode::VALUE_NODE &&  node1->exprNodeType() == ExprNode::VALUE_NODE)
			return;




//		if (node1->addrName() != node0->addrName())
//			return;

		switch (input_node->get_subcode()) {
		case OpNode::PLUS:
			if (node1->exprNodeType() == ExprNode::VALUE_NODE)
		{
			node2 = opd[1];
			node1 = opd[2];
		}
		case OpNode::MINUS:
			if ((Type::isInt(node2->value()->type()->tag()) && node2->value()->ival() == 0)||
					(Type::isFloat(node2->value()->type()->tag()) && node2->value()->dval() == 0)){
				if (node1== node0 )
					goto remove_instruction;
				else {
					window->clear();
					window->push_back(new ImmCode(ImmCode::EXPR,
							OpNode::ASSIGN, node0, node1));
					*updated = true;
				}
			}
			break;
		case OpNode::MULT:
			if (node1->exprNodeType() == ExprNode::VALUE_NODE)
		{
			node2 = opd[1];
			node1 = opd[2];
		}
		case OpNode::DIV:
			if ((Type::isInt(node2->value()->type()->tag()) && node2->value()->ival() == 1) ||
			(Type::isFloat(node2->value()->type()->tag()) && node2->value()->dval() == 1)){
				if (node1== node0 )
					goto remove_instruction;
				else {
					window->clear();
					window->push_back(new ImmCode(ImmCode::EXPR,
							OpNode::ASSIGN, node0, node1));
					*updated = true;
				}
			}
			break;
		default:
			break;

		}
	}
	return;

	remove_instruction:
	window->clear();
	*updated = true;
	return;
}


/*void CodeOptimizer::peephole_staticEvaluation(vector<ImmCode*>* window,
		bool* updated) {
	/*Optimize for
	 *
	 * Modify:
	 * 		a = ValueNode + ValueNode
	 * 		if ( 1 == 2 ) goto Lx
	 *
	 * To:
	 * 		a = ValueNode
	 * 		//Removed
	 */
/*
	if (window->size() != 1)
		return;

	ImmCode *code = window->at(0);

	switch (code->getType()) {
	case ImmCode::EXPR: {
		ExprNode** opd = (ExprNode**) (code->get_opnd());
		ExprNode* node1 = opd[1];
		ExprNode* node2 = opd[2];
		switch (code->get_subcode()) {
		case OpNode::PLUS:
		case OpNode::MINUS:
		case OpNode::MULT:
		case OpNode::DIV:
			cout << "aaa";

			break;
		default:
			break;
		}
		break;
	}
	default:
		break;
	}
*/
//}
